package src.stack_queue;

import java.util.ArrayDeque;

public class no1047 {
    //删除字符串中的所有相邻重复项，比如abbaca 变成 ca，把abba消除了
    public static void main(String[] args) {
        String s = "abbbabaaa";
        System.out.println(removeDuplicates2(s));

    }

    //使用 Deque 作为堆栈
    public static String removeDuplicates1(String s) {
        ArrayDeque<Character> deque = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!deque.isEmpty() && deque.peek() == c) {
                deque.pop();
            } else {
                deque.push(c);
            }
        }

        // 最终栈中的元素是ca，出栈变为ac，还要反转一下
        StringBuilder sb = new StringBuilder();
        while (!deque.isEmpty()) {
            sb.append(deque.pop());
        }
        sb.reverse();
        return sb.toString();
    }

    //拿字符串直接作为栈，省去了栈还要转为字符串的操作。用一个top指针表示栈顶，移动top表示入栈、出栈
    public static String removeDuplicates2(String s) {
        StringBuilder sb = new StringBuilder();
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (top >= 0 && sb.charAt(top) == c) {
                //当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
                sb.deleteCharAt(top);
                top--;
            } else {
                sb.append(c);
                top++;
            }
        }
        return sb.toString();
    }

    //双指针
    public static String removeDuplicates3(String s) {
        char[] c = s.toCharArray();
        int slow = 0;
        int fast = 0;
        while (fast < s.length()) {
            //直接用fast指针覆盖slow指针的值
            c[slow] = c[fast];
            //遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
            if (slow > 0 && c[slow] == c[slow - 1]) {
                slow--;
            } else {
                slow++;
            }
            fast++;
        }
        return new String(c, 0, slow);
    }
}
